package com.example.demo.leetcode;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class _76_最小覆盖子串 {

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";

        String s1 = "a";
        String t1 = "a";

        String s2 = "a";
        String t2 = "aa";

        String str = minWindow(s2, t2);
        System.out.println(str);
    }

    private static Map<Character, Integer> map = new HashMap<>();
    private static Map<Character, Integer> temp = new HashMap<>();

    public static String minWindow(String s, String t) {
        for (int i = 0; i < t.length(); i++) {
            Integer orDefault = map.getOrDefault(t.charAt(i), 0);
            map.put(t.charAt(i), ++orDefault);
        }
        String res = "";
        int left = 0;
        int right = 0;

        //第一个字母
        Integer num = temp.getOrDefault(t.charAt(right), 0);
        temp.put(t.charAt(right), ++num);

        while (left <= right) {
            if (check()) {
                if (res != null && res.length() > (right - left)) {
                    if (res.length() > (right - left + 1)) {
                        res = s.substring(left, right + 1);
                    }
                } else {
                    res = s.substring(left, right + 1);
                }

                Integer orDefault = temp.getOrDefault(s.charAt(left), 0);
                if (orDefault - 1 == 0) {
                    temp.remove(s.charAt(left));
                } else {
                    temp.put(s.charAt(left), orDefault - 1);
                }
                left++;
            } else {
                right++;
                if (right > s.length() - 1) {
                    return res;
                }
                Integer orDefault = temp.getOrDefault(s.charAt(right), 0);
                temp.put(s.charAt(right), ++orDefault);
            }
        }
        return res;
    }


    public static boolean check() {
        Iterator<Map.Entry<Character, Integer>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Character, Integer> next = iterator.next();
            Integer value = temp.get(next.getKey());
            if (value == null || value < next.getValue()) {
                return false;
            }
        }
        return true;
    }

}
